home *** CD-ROM | disk | FTP | other *** search
- Path: news.umbc.edu!not-for-mail
- From: schlein@umbc.edu (Jonas J. Schlein)
- Newsgroups: comp.lang.c
- Subject: Re: Loop Invariant
- Date: 26 Jan 1996 14:01:36 -0500
- Organization: University of Maryland Baltimore County
- Message-ID: <4eb8eg$7lg@umbc9.umbc.edu>
- References: <4e42pg$2oq@sanjuan.islandnet.com>
- NNTP-Posting-Host: umbc9.umbc.edu
- NNTP-Posting-User: schlein
-
- Jason Klinke <jklinke@uvaix.uvic.ca> wrote:
- |> I'm having difficulty coming up with a loop invariant that I can prove, for
- |> the following code which computes the sum of the integers in the array
- |> A[0..n-1] :
- |>
- |> -----------
- |> sum = 0;
- |> for (i = 0; i < n; i++)
- |> sum = sum + A[i];
- |> -----------
- |>
- |> Any help with this invariant and its proof is appreciated.
-
- Do it by induction...Verify that it works for the sum of the integers in
- am empty array (or an array with only 1 element). Then assume it works
- for any array with n-1 elements and from that prove that this implies
- it also works for an array with n elements.
-
- Basically this idea is called mathematical induction. There is a weak and
- strong form. I can't believe your teacher did not tell you about this
- since that is obviously what is probably intended.
- --
- "If it wasn't for C, we would be using BASI, PASAL, and OBOL."
-
- Jonas J. Schlein (schlein@gl.umbc.edu)
-